#include <stdio.h>
typedef int ElementType;
void Swap(ElementType *a, ElementType *b) {
    ElementType t = *a;
    *a = *b;
    *b = t;
}
void PerDown(ElementType A[],int p, int N) {
    int Parent,Child;
    ElementType X;
    X = A[p];
    for(Parent = p;(Parent*2+1) < N;Parent = Child) {
        Child = Parent*2+1;
        if((Child!=N-1) && (A[Child]<A[Child + 1])) {
            Child++;
        }
        if(X >= A[Child]) break;
        else {
            A[Parent] = A[Child];
        }

    }
    A[Parent] =  X;
}
void HeapSort(ElementType A[],int N) {
    int i;
    for(i = N/2-1;i>=0;i--) {
        PerDown(A,i,N);
    }
    for(i = N-1;i>0;i--) {
        Swap(&A[0],&A[i]);
        PerDown(A,0,i);
    }
}
int main() {
    int arr[] = {2,2,3,4,9,1,2,7,6,45,12,63,12};
    HeapSort(arr,13);
    for (int i = 0; i < 13; ++i) {
        printf("%d ",arr[i]);
    }
    return 0;
}
